package com.linchong.stackqueue.hard;

import java.util.Stack;

/**
 * @author linchong
 * @version 1.0
 * @Date: 2020-12-01 17:32
 * @Description: BasicCalculator$224-计算器
 * 实现一个基本的计算器来计算一个简单的字符串表达式的值。
 *
 * 字符串表达式可以包含左括号 ( ，右括号 )，加号 + ，减号 -，非负整数和空格  。
 *
 * 示例 1:
 *
 * 输入: "1 + 1"
 * 输出: 2
 * 示例 2:
 *
 * 输入: " 2-1 + 2 "
 * 输出: 3
 * 示例 3:
 *
 * 输入: "(1+(4+5+2)-3)+(6+8)"
 * 输出: 23
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/basic-calculator
 *
 */
@SuppressWarnings("unused")
public class BasicCalculator {

	void compute(Stack<Integer> numberStack,Stack<Character> operationStack){
		if(numberStack.size()<2){
			return;
		}
		int num2 = numberStack.pop();
		int num1 = numberStack.pop();
		Character operator = operationStack.pop();
		if(operator=='+'){
			numberStack.push(num1+num2);
		}else if(operator=='-'){
			numberStack.push(num1-num2);
		}
	}

	public int calculate(String s) {
		//状态机-起始状态
		final int stateBegin = 0;
		//状态机-数字状态
		final int numberState = 1;
		//状态机-操作符状态
		final int operationState = 2;
		//数字
		Stack<Integer> numberStack=new Stack<>();
		//操作符
		Stack<Character> operationStack=new Stack<>();

		int number = 0;

		int state = stateBegin;
		//是否可以计算
		int computeFlag = 0;
		char[] chars = s.toCharArray();
		for (int i = 0; i < chars.length; i++) {
			if(chars[i]==' '){
				continue;
			}
			switch (state){
				case stateBegin:
					if(chars[i]>='0'&&chars[i]<='9'){
						state = numberState;
					}else{
						state = operationState;
					}
					i--;
					break;
				case numberState:
					if(chars[i]>='0'&&chars[i]<='9'){
						number = number*10+chars[i]-'0';
					}
					else{
						numberStack.push(number);
						if(computeFlag==1){
							//计算
							compute(numberStack,operationStack);
						}
						number = 0;
						i--;
						state = operationState;
					}
					break;
				case operationState:
					if(chars[i]=='+'||chars[i]=='-'){
						operationStack.push(chars[i]);
						computeFlag = 1;
					}
					else if(chars[i]=='('){
						state = numberState;
						computeFlag = 0;
					}
					else if(chars[i]>='0' && chars[i]<='9'){
						state = numberState;
						i--;
					}
					else if(chars[i]==')'){
						//计算
						compute(numberStack,operationStack);
					}
					break;
				default:
					break;
			}
		}
		if(number != 0){
			numberStack.push(number);
			//计算
			compute(numberStack,operationStack);
		}
		if(number == 0 && numberStack.isEmpty()){
			return 0;
		}
		return numberStack.pop();
		
	}












}
